package chapter16;


/**
 * 贪心-赫夫曼编码
 * <p>
 * 核心:
 * 0. extractMin,每次选择最小的节点
 */
public class Huffman {

    public static HuffmanNode huffman(HuffmanNode[] A) {
        int n = A.length;

        HuffmanOperation huffmanOperation = new HuffmanOperation(A);
        for (int i = 1; i <= n - 1; i++) {
            HuffmanNode z = new HuffmanNode();
            HuffmanNode left = huffmanOperation.extractMin();
            HuffmanNode right = huffmanOperation.extractMin();
            z.left = left;
            z.right = right;
            if (left != null) {
                left.weight = 0;
                z.value += left.value;
            }
            if (right != null) {
                right.weight = 1;
                z.value += right.value;
            }
            huffmanOperation.insert(z);
        }
        return huffmanOperation.extractMin();
    }

    /**
     * 构建树
     */

    public static class HuffmanOperation {

        HuffmanNode[] huffmanNodes;

        public HuffmanOperation(HuffmanNode[] A) {
            quickSort(A, 0, A.length - 1);
            this.huffmanNodes = A;
        }

        public HuffmanNode extractMin() {
            HuffmanNode min = huffmanNodes[0];
            HuffmanNode[] newArr = new HuffmanNode[huffmanNodes.length - 1];
            System.arraycopy(huffmanNodes, 1, newArr, 0, huffmanNodes.length - 1);
            huffmanNodes = newArr;
            return min;
        }

        public void insert(HuffmanNode node) {
            int n = huffmanNodes.length;
            HuffmanNode[] newArr = new HuffmanNode[huffmanNodes.length + 1];
            System.arraycopy(huffmanNodes, 0, newArr, 0, huffmanNodes.length);
            newArr[n] = node;
            huffmanNodes = newArr;
            quickSort(huffmanNodes, 0, huffmanNodes.length - 1);
        }

        public void quickSort(HuffmanNode[] A, int p, int r) {
            if (p < r) {
                int q = partition(A, p, r);
                quickSort(A, p, q - 1);
                quickSort(A, q + 1, r);
            }
        }

        public int partition(HuffmanNode[] A, int p, int r) {
            HuffmanNode x = A[r];
            int i = p - 1;
            int k = 0;
            for (int j = p; j <= r - 1; j++) {
                if (A[j].value < x.value) {
                    i++;

                    HuffmanNode temp = A[i];
                    A[i] = A[j];
                    A[j] = temp;
                } else if (A[j].value == x.value) {
                    k++;
                    if (k == r - p) {
                        return (r + p) / 2;
                    }
                }
            }
            HuffmanNode temp = A[i + 1];
            A[i + 1] = A[r];
            A[r] = temp;
            return i + 1;
        }
    }

    public static class HuffmanNode {
        public HuffmanNode left;
        public String key;
        public int value;
        public HuffmanNode right;
        public int weight;

        public HuffmanNode() {
        }

        public HuffmanNode(String key, int value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return "HuffmanNode{" +
                    "left=" + left +
                    ", key='" + key + '\'' +
                    ", value=" + value +
                    ", right=" + right +
                    ", weight=" + weight +
                    '}';
        }
    }
}
